#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        unordered_map<char, int> char_map;
        for (char item : chars) {
            if (char_map.find(item) == char_map.end()) {
                char_map[item] = 1;
            } else {
                char_map[item]++;
            }
        }
        int ans = 0;
        for (string word : words) {
            unordered_map<char, int> map;
            for (char item : word) {
                if (map.find(item) == map.end()) {
                    map[item] = 1;
                } else {
                    map[item]++;
                }
            }
            bool valid = true;
            for (pair<char, int> item : map) {
                if (char_map.find(item.first) == char_map.end()) {
                    valid = false;
                    break;
                } else if (char_map[item.first] < item.second) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                ans += word.size();
            }
        }
        return ans;
    }
};

class Solution1 {
private:
    bool dfs(string& word, unordered_map<char, int> char_map, int i) {
        if (i == word.size()) {
            return true;
        }
        if (char_map[word[i]] == 0) {
            return false;
        }
        char_map[word[i]]--;
        if (!dfs(word, char_map, i + 1)) {
            char_map[word[i]]++;
            return false;
        }
        char_map[word[i]]++;
        return true;
    }
public:
    int countCharacters(vector<string>& words, string chars) {
        unordered_map<char, int> char_map;
        for (char item : chars) {
            if (char_map.find(item) == char_map.end()) {
                char_map[item] = 1;
            } else {
                char_map[item]++;
            }
        }
        int ans = 0;
        for (string word : words) {
            if (dfs(word, char_map, 0)) {
                ans += word.size();
            }
        }
        return ans;
    }
};

class Solution2 {
private:
    bool dfs(string& word, int* char_map, int i) {
        if (i == word.size()) {
            return true;
        }
        if (char_map[word[i] - 'a'] == 0) {
            return false;
        }
        char_map[word[i] - 'a']--;
        if (!dfs(word, char_map, i + 1)) {
            char_map[word[i] - 'a']++;
            return false;
        }
        char_map[word[i] - 'a']++;
        return true;
    }
public:
    int countCharacters(vector<string>& words, string chars) {
        int char_map[26] = {0};
        for (char item : chars) {
            char_map[item - 'a']++;
        }
        int ans = 0;
        for (string word : words) {
            if (dfs(word, char_map, 0)) {
                ans += word.size();
            }
        }
        return ans;
    }
};

class Solution3 {
public:
    int countCharacters(vector<string>& words, string chars) {
        int char_map[26] = {0};
        for (char item : chars) {
            char_map[item - 'a']++;
        }
        int ans = 0;
        for (string word : words) {
            int map[26] = {0};
            for (char item : word) {
                map[item - 'a']++;
            }
            bool valid = true;
            for (int i = 0; i < 26; i++) {
                if (map[i] > char_map[i]) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                ans += word.size();
            }
        }
        return ans;
    }
};